// 5. 最长回文子串
function palindrome(s, left, right){
    while(left>=0 && right<s.length && s[left] === s[right]){
        left--;
        right++;
    }
    return s.substring(left+1, right);
}

// 爬楼梯
function climbStairs(n) {
    const dp = [];
    dp[0] = 1; // 爬0个台阶 1
    dp[1] = 1; // 爬一个台阶 1 
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];

    }
    return dp[n];
}

// 买卖股票的最佳时机
// 暴力超时
function maxProfit(prices) {
    const length = prices.length;
    let res = 0;
    for (let i = 0; i < length; i++) {
        for (let j = i; j < length; j++) {
            res = Math.max(res, prices[j] - prices[i]);
        }
    }
    return res;
}
function maxProfit(prices) {
    const length = prices.length;
    let res = 0;
    let minPrice = Infinity; // 正无穷和负无穷,JS 中对应的表示方式为: +Infinity(或者Infinity) 和 - Infinity
    for (let i = 0; i < length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > res) {
            res = prices[i] - minPrice;
        }
    }
    return res;
}

const dp = Array.from(Array(row), () => Array(column).fill(false));


// 300. 最长递增子序列

const lengthOfLIS = (nums) => {
    let dp = Array(nums.length).fill(1);
    let result = 1;

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        result = Math.max(result, dp[i]);
    }

    return result;
};

// 1143. 最长公共子序列
var longestCommonSubsequence = function (text1, text2) {
    let length1 = text1.length;
    let length2 = text2.length;
    let dp = Array(length1 + 1).fill(0).map(() => new Array(length2 + 1).fill(0));
    for (let i = 1; i <= length1; i++) {
        for (let j = 1; j <= length2; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[length1][length2];
};

// 53. 最大子数组和
var maxSubArray = function(nums) {
    const length = nums.length;
    let dp = [];
    dp[0] = nums[0];
    let res = nums[0];
    for(let i = 1; i< length; i++){
        dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
        res = Math.max(res, dp[i]);
    }
    return res;
};